Compute Degrees - Educational Content

Calculating local connectivity for each vertex.

For an undirected graph, the degree $\deg(u)$ is simply the number of neighbors, which is the size of its adjacency list, $|adj[u]|$.
For a directed graph, the out-degree is the size of the adjacency list, $|adj[u]|$. The in-degree is more costly to compute, as it requires scanning all other vertices' adjacency lists to see who points to $u$.
Self-loops are a special case: they add 2 to an undirected degree but only 1 to the in-degree and 1 to the out-degree in a directed graph.

Python: Degree Calculation Functions

def degree_undirected(adj,u):
    return len(adj[u])

def outdeg(adj,u):
    return len(adj[u])

def indeg(adj,u):
    # Inefficient scan, better to precompute
    return sum(1 for x in adj if u in adj[x])